Autômatos Celulares
 

Definição Informal

Uma automação celular é um sistema dinâmico, onde o tempo e o espaço são discretos. O sistema é divido em células, seus elementos básicos. Tais células possuem um conjunto finito de estados predefinidos e um conjunto de condições necessárias para a mudança de estados. Os estados das células são alterados conforme um conjunto de regras de transição. Tais regras de transição são baseadas no estado atual da célula e de suas vizinhas. É válido ressaltar que os estados são alterados ao mesmo tempo para todas as células. Por exemplo, o estado da célula c_i no tempo t, depende apenas do seu estado e dos estados das células vizinhas no tempo t-1. A vizinhança das células são definidas local e uniformemente (se uma célula tem n vizinhos, todas as células terão).
 

Pequeno Exemplo

Um exemplo simples seria a propagação de um pulso numa corda. Dividimos a corda em pequenos pedaços, que chamaremos de células. Temos que para uma célula sofrer alteração no seu estado, ou seja, para um pulso ser propagado, é preciso que algum de seus vizinhos seja alterado (ou exitado) no tempo anterior. Definimos o vizinhos de cada célula como as mais imediatamente à direita e à esqueda. Então podemos definir um conjunto de duas regras básicas:

• Se uma célula está exitada no tempo t, ela não estará no tempo t+1.
• Se uma célula não está exitada no tempo t, ela ficará no tempo t+1 se pelo menos um vizinho seu está exitado no tempo t.

Abaixo encontra-se um esquemático deste exemplo, onde é mostrado como funciona a transição de estados das células.

Definição Formal de Autômatos Celulares

Seja

• L um reticulado regular ( os elementos de L são chamados de células),
• S um conjunto finito de estados,
• N um conjunto finito (de tamanho |N| = n) de índices vizinhos tal que para todo r em N e todo c em L: r+c está em L.
• f: Sⁿ -> S uma função de transição.

Definimos aqui que um reticulado é regular se é uma rede periódica de uma espaço de dimensão d, e os elementos do reticulado, as células, preenchem o espaço completamente, e ao se translatar o reticulado em d direções independentes, obtemos o mesmo reticulado.

Uma configuração C_t: L -> S é uma função que associa uma estado a cada célula do reticulado. O efeito da função de transição f deve mudar a configuração C_t na nova configuração Ct₊₁ de acordo com a seguinte equação:

C_t+1(r) = f( {C_t(i): i em N(r) È {C_t(r)}¹ } ),
 
 

¹ Algumas definições de autômatos celulares levam em consideração o estado atual da célula a ser modificada, outras não, portando esse conjunto que contém a configuração da célula atual pode fazer parte ou não do argumento da função de transição.

Onde N(r) é o conjunto de vizinhos da célula r.

N(r) = { i em L: r-i em N }²

² A definição dos vizinhos de cada célula vai depender do problema a ser resolvido.

Em aplicações práticas, os reticulados são restringidos a um tamanho finito. Alguns problemas causados por essas limitações são resolvidos na próxima seção.